While typically memory devices, such as random access memories (RAMs) and read only memories (ROMs) access single entries according to an applied addresses, other types of memory devices can provide a matching function with respect all entries in a device. One such type of a memory device is the content addressable memory (CAM) device.
Conventional CAM devices can store a number of data values, each in one entry. Data values stored in the entries may then be compared to an applied comparand value (also referred to as a key) to generate a match indication. The relatively rapid speed at which CAM devices can compare multiple entries to an applied comparand value has resulted in CAMs enjoying widespread use in various applications, such as packet processing, as but one example. A match indication generated by a conventional CAM device can typically take only one of two possible results: match (HIT) or no match (MISS).
Conventional CAM devices include both binary CAM devices and ternary CAM devices. Conventional binary CAM devices typically include entries that can each store a data value having a number of data bits. In most cases, a match indication can be generated when all bits of a comparand value match all the bits of an entry. Thus, a conventional binary CAM device can include a number of binary CAM cells, each of which can operate to provide, on a bit-wise basis, a bit compare result of equal “=” (stored data bit “V” matches corresponding compare data bit “CD”) or not equal “!=” (stored data bit “V” matches corresponding compare data bit CD).
Conventional ternary CAM devices may typically include entries having data bits, some or all of which may be masked from a compare operation. Thus, a conventional ternary CAM device can include a number of ternary CAM cells, each of which can operate to provide, on a bit-wise basis, a bit compare result of “=”, “!=”, or “don't care” (indicate data value is equal regardless of compare data value).
To better understand various aspects of the embodiments, examples of conventional CAM devices will be now be described. Referring to FIG. 21, one general configuration for a conventional CAM device is set forth in block diagram and designated by the general reference character 2100. FIG. 21 shows a CAM device row, which can be repeated to form a CAM array with match circuits. A conventional CAM row 2100 can include a match line 2102 that can be precharged to a high potential by a precharge circuit 2104. Connected between the match line 2102 and a low voltage can be a number of CAM cells 2106-1 to 2106-N, each of which can store data bit value. Each CAM cell (2106-1 to 2106-N) can receive a corresponding comparand bit value by way of a pair of comparand lines (CD1/BCD1 to CDN/BCDN).
In operation, a match line 2102 can be precharged to a high voltage level. Then, each CAM cell (2106-1 to 2106-N) can perform an exclusive NOR type operation with respect to a stored data bit value and the corresponding comparand bit value. If a match does not exist between at least one bit, a discharge path is created through the CAM cell of the non-matching bit and the match line potential falls. This can be detected by a match sense amplifier (MSA) 2108 as a “miss”. In contrast, if a match exists between all bits, no discharge path is created and the match line remains high. This can be detected by a match sense amplifier (MSA) 2108 as a “hit”.
In the case of a “binary” CAM cell, bit match and misses can be based solely on a stored data bit value “V” and compare bit value “CD”. In the case of “ternary” CAM cells, bit match and misses can additionally be based on a “masking” of bit values, which can force a match or miss regardless of the stored data bit value. More particularly, in the case of a valid/mask (V/M) ternary CAM cell, if a mask bit M has one value (e.g., high), bit compare result can be “always match”. Similarly, in the case of an two value (X/Y) encoded ternary CAM cell, if two data bits have one value (e.g., X=Y=low), bit compare result will be “always match”, but if two data bits have another value (e.g., X=Y=high), bit compare result will be “always miss”.
Various examples of conventional CAM cells that provide an XNOR/XOR type function are set forth in FIGS. 22A to 22D. FIG. 22A is a schematic diagram showing one example of a conventional binary CAM cell 2200. When a compare data value (CD) matches a stored data value (V), a discharge transistor N1 can provide a low impedance path to a low supply voltage, which can pull the potential of the match line lower. Conversely, when a compare data value (CD) matches a stored data value (V), a discharge transistor N1 can have a high impedance, and hence isolate a match line from the low supply voltage.
FIG. 22B is a schematic diagram showing one example of a conventional V/M ternary CAM cell 2202. V/M ternary CAM cell 2202 operates in the same general fashion binary CAM cell 2200, with the addition of a mask transistor N2 in the discharge path. FIG. 22C is a schematic diagram showing another example of a conventional V/M ternary CAM cell 2204. V/M ternary CAM cell 2204 includes series connected transistors having gates that each receive a data bit value or its complement (V or !V) and a compare data bit value or its complement (CD or BCD).
FIG. 22D is a schematic diagram showing one example of a conventional X/Y ternary CAM cell 2206. In the arrangement of FIG. 22D, the bit combinations of X and Y yield the following results: X=0/Y=1, match CD=1; X=1/Y=0, match CD=0; X=Y=0, always match; and X=Y=1, always miss.
The above conventional examples have demonstrated a “NOR”, or “wire NOR” approach to match determinations. That is, in the event a miss in any bit location generates an overall miss result for the entire entry. An alternate approach is shown in FIGS. 23 and 24.
FIG. 23 shows a conventional CAM device row, which can be repeated to form a CAM array with match circuits. A conventional CAM row 2300 can represent an AND or NAND approach to match determinations. That is, only in the event that a match occurs in every bit location will a match exist for the overall entry.
A conventional NAND CAM row approach 2300 can include a number of CAM cells 2302-1 to 2302-N arranged in series between a high supply and a match sense amplifier 2304. In operation, CAM cell (2302-1 to 2302-N) can perform an NAND type operation with respect to a stored data bit value and the corresponding comparand bit value. If a match does not exist in the cell, a high impedance path is created, preventing a high potential from propagating to match sense amplifier 2304. In contrast, if a match exists between all bits, all CAM cells (2302-1 to 2302-N) of the row can present low impedance paths allowing a high potential to propagate to sense amplifier (MSA) 2304 and be detected as a “hit”.
FIG. 24 is a schematic diagram showing one example of a conventional ternary NAND type CAM cell 2400 that can be included in an arrangement like that of FIG. 23. Prior a compare operation, a precharge device N7 can preset nodes between adjacent TCAM cells to a low potential. In a compare operation, when a compare data value (CD) matches a stored data value (V) or a match bit has a particular value (e.g., M=0), a low impedance path can be created through the NAND type CAM cell 2400.
Conventional CAM devices can provide both binary and ternary matching capabilities. However, in certain applications is may be desirable to have more complex types of operations. For example, in some cases it may be desirable to determine if a given comparand value, or portion thereof, falls within a given range.
U.S. Pat. No. 7,206,212 issued on Apr. 17, 2007, titled CONTENT ADDRESSABLE MEMORY (CAM) DEVICE WITH ENTRIES HAVING TERNARY MATCH AND RANGE COMPARE FUNCTIONS, by Richard Chou, discloses a CAM that can have a value match mode and a range match mode. In a range match mode, a comparand value can be compared to an upper and lower range limit.
Co-pending U.S. patent application Ser. No. 10/180,357, titled RANGE COMPARE CIRCUIT FOR SEARCH ENGINE, by Richard Chou, discloses a range matching circuit that receives a first range value from a first range store and a second range value from a second range store, and determines if a comparand value is within such a range.
In light of the above, it would be desirable to arrive at a compact comparator memory structure that can provide compare operations beyond equal “=” and not equal Such additional capabilities may help improve processing capabilities for various applications, including but not limited to network search engines (NSEs), image processing, database search acceleration, to name but a few.
It would also be desirable if such additional compare operations could be bit maskable, in the same general fashion as a conventional ternary CAM device.